package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/
 *  字典树 字节高频题
 * author: hongchen.liao
 * date:  2022/8/5
 */
public class _440_Kth_Smallest_in_Lexicographical_Order {

    class Solution {
        public int findKthNumber(int n, int k) {
            int curr = 1;
            k--;
            while(k > 0){
                int steps = getSteps(curr, n);
                if(steps <= k){
                    k -= steps;
                    curr++;
                }else{
                    curr = curr * 10;
                    k--;
                }
            }
            return curr;
        }

        int getSteps(int curr, long n){
            int steps = 0;
            long first = curr;
            long last = curr;
            while(first <= n){
                steps += Math.min(last, n) - first + 1;
                first = first * 10;
                last = last * 10 + 9;
            }
            return steps;
        }
    }

}
